/* Copyright 2011 Tobias Marschall, Email: tm@cwi.nl 
 * 
 * This file is part of string-cover.
 *
 * string-cover is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * string-cover is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with string-cover.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef BRANCHANDBOUNDNODE_H_
#define BRANCHANDBOUNDNODE_H_

#include <iostream>
#include <boost/dynamic_bitset.hpp>

#include "ProblemInstance.h"
#include "Multipliers.h"

/** A node in the branch and bound tree, i.e. a class encapsulating a set of
 *  included strings, a set of forbidden strings, and a priority. The solver can
 *  then decide which node to examine next based on the priority. */
class BranchAndBoundNode {
private:
	double priority;
	const ProblemInstance& instance;
	boost::dynamic_bitset<> included;
	boost::dynamic_bitset<> forbidden;
	bool is_root;
	Multipliers* multipliers;
public:
	/** Constructor creating the root node of the branch-and-bound tree. */
    BranchAndBoundNode(const ProblemInstance& problem);
    /** Copy constructor. */
    explicit BranchAndBoundNode(const BranchAndBoundNode& node);
    virtual ~BranchAndBoundNode();
    const ProblemInstance& getProblemInstance() const;
    double getPriority() const;
    void setPriority(double priority);
    void forbidSubstring(size_t substring_index);
    void includeSubstring(size_t substring_index);

    bool isForbidden(size_t substring_index) const;
    bool isIncluded(size_t substring_index) const;

    const Multipliers* getMultipliers() const;
    void setMultipliers(std::auto_ptr<Multipliers> multipliers);

    /** Returns the sum of weights of included substrings. */
    double weightOfIncluded() const;

    const ProblemInstance& getInstance() const;

    friend std::ostream& operator<<(std::ostream& os, const BranchAndBoundNode& node);
    bool isRoot() const;
};

typedef std::pair<double,BranchAndBoundNode*> priority_and_node_t;

#endif /* BRANCHANDBOUNDNODE_H_ */
